package 剑指offer;

import 抽象数据类型.ListNode;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-25
 */
public class 链表中环的入口节点 {
    public static void main(String[] args) {
        ListNode l1 = null;
       /* l1 = MergeListNode.proList(new int[]{5, 9, 7, 5,
                7, 1, 2, 6, 4, 2, 7, 8, 9, 6, 1, 6, 6, 1, 1, 4, 2, 9, 5, 5, 0, 4, 6, 3, 0, 4, 3, 5, 6, 7, 0, 5, 5, 4, 4, 0}, 0, l1);
       */
        l1 = new ListNode(3);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(0);
        l1.next.next.next = new ListNode(-4);
        l1.next.next.next.next = l1.next.next;

        System.out.println(detectCycle(l1).val);
    }

    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode one = head.next;
        ListNode two = head.next.next;
        ListNode three = head;
        while (one != two) {
            if (one == null || two == null || two.next == null) {
                return null;
            }
            one = one.next;
            two = two.next.next;

        }
        while (three != one) {
            one = one.next;
            three = three.next;
        }
        return one;
    }
}
